#include <bits/stdc++.h>
#define int long long
using namespace std;
int mod,n,m,s[210][40010],t;
int read(){
    int s=0;
    char ch=getchar(),last=' ';
    while(ch<'0'||ch>'9')
        last=ch,ch=getchar();
    while(ch>='0'&&ch<='9')
        s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return last=='-'?-s:s;
}
int power(int a,int b){
    int res=1;
    while(b){
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod)
        a-=mod;
}
signed main(){
    freopen("pr.in","r",stdin);
    freopen("pr.out","w",stdout);
    mod=read();
    t=read();
    while(t--){
        n=read(),m=read();
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n*m;j++)
                s[i][j]=0;
        s[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++)
                for(int l=0;l+j<=n*m;l++)
                    if(s[i-1][l])
                        add(s[i][l+j],s[i-1][l]);
        }
        int sum=0,tot=0;
        for(int i=0;i<=n*m;i++){
            add(tot,sum*s[n][i]%mod);
            add(sum,s[n][i]);
        }
        printf("%lld\n",(tot*power(power(m+1,n*2),mod-2)%mod));
    }
    return 0;
}
